perm filename 4.6[0,BGB] blob
sn#075336 filedate 1974-02-14 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00011 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 4.6 CRE NODE FORMATS.
C00006 00003 CRE Node Rellocation Bits.
C00008 00004 1. VECTOR & 2. ARC NODE FORMAT.
C00013 00005 3. POLYGON NODE FORMAT.
C00017 00006 4. SHAPE NODE FORMAT.
C00022 00007 5. LEVEL NODE FORMAT.
C00025 00008 6. IMAGE NODE FORMAT.
C00029 00009 7. FILM NODE FORMAT.
C00032 00010 8. EMPTY NODE FORMAT.
C00035 00011 DATA STRUCTURE: IMAGE ARRAYS.
C00039 ENDMK
C⊗;
4.6 CRE NODE FORMATS.
DATA STRUCTURE: TYPE BITS.
Each node has a word reserved for a boolean vector of 36
values, or bits. The first eighteen bits are called the type bits
and are individually named as follows:
_____________________________________________________________________
for 0 WESBIT westward vector.
vectors 1 SOUBIT southward vector.
only 2 EASBIT eastward vector.
3 NORBIT northward vector.
_____________________________________________________________________
4 NFUSE NTIME polygon fusion.
5 NFISS NTIME polygon fission.
for 6 NEXCT NTIME polygon exact match.
polygons
only 7 PFUSE PTIME polygon fusion.
8 PFISS PTIME polygon fission.
9 PEXCT PTIME polygon exact match.
_____________________________________________________________________
10 HOLBIT Hole polygon bit.
modify 11 ARCBIT Arc vector bit.
_____________________________________________________________________
12 SBIT Shape node bit.
13 VBIT Vertex node bit.
14 PBIT Polygon node bit.
kind
15 LBIT Level node bit.
16 IBIT Image node bit.
17 FBIT Film node bit.
_____________________________________________________________________
The first four bits WESBIT, SOUBIT, EASBIT and NORBIT apply
only to vectors and indicate the direction of the vector. The next
six bits NFUSE, NFISS, NEXCT, PFUSE, PFISS, PEXCT are set by the
polygon compare routine to indicate the kind of time mating found;
where N and P mean negative time or postive time linkage; fusion
means that the given polygon and another polygon fuse to form the
time polygon, two into one; fission means the given polygon splits,
one into two; and exact means that the given polygon matchs one for
one with its time polygon.
The next two bits HOLBIT and ARCBIT indicate distinguished
polygons and vectors respectively. Only one of the last six bits:
SBIT, VBIT, PBIT, LBIT, IBIT and FBIT may be on in a node. These
bits indicate the node's type.
CRE Node Rellocation Bits.
The next eighteen bits are called the reloc bits and
indicate whether or not a link is stored in a particular position of
the node. The rellocation bits are used to compact the CRE node
space for output.
18 unused
19 CAR(WORD0)
20 CDR(WORD0)
21 unused
22 CAR(WORD1)
23 CDR(WORD1)
24 unused
25 CAR(WORD3)
26 CDR(WORD3)
27 unused
28 CAR(WORD4)
29 CDR(WORD4)
30 unused
31 CAR(WORD5)
32 CDR(WORD5)
33 unused
34 CAR(WORD6)
35 CDR(WORD6)
The CAR of a word is the left half. The CDR of a word is the
right half. In the node diagrams the rellocation of each word is
indicated directly to its right as 0, 1, 2 or 3 meaning no
rellocation, left only, right only, and rellocate both halves,
respectively.
1. VECTOR & 2. ARC NODE FORMAT.
_____________________________________________
word | CW | CCW |
0 | vector ring | 3
_____|___________________|___________________|
word | DAD | SON |
1 | polygon | arc or vector | 3
_____|___________________|___________________|
word | type | reloc |
2 | | 33 0003 |
_____|___________________|___________________|
word | row | col |
3 | 0000.00 | 0000.00 | 0
_____|___________________|___________________|
word | cntrst | ncnt |
4 | | length | 0
_____|___________________|___________________|
word | |
5 | zdepth | 0
_____|_______________________________________|
word | | |
6 | NTIME time line PTIME | 3
_____|___________________|___________________|
The format of vectors and arcs is identical. Inside CRE the
term "vector" has the connotation of being strictly a horizontal or
vertical generated by the contouring step; whereas an arc is a
vector generated by the smoothing step. Vectors contain the
fundamental geometric datum of an image locus. The image locus is
stored in the halfword datums named row and col, which contain the
row and column of a point in units 1/64 of a pixel. (A "pixel" is a
"picture element"). Vectors and arcs also contain the photometric
datum of edge contrast.
Vectors always belong to a polygon node, a pointer to the
polygon of each vector is stored in the link named DAD; as members
of a polygon the vectors form a loop which is always connected so that
each vertex has a neighboring vertex in the clockwise and in the
counter clockwise directions about the polygon's perimeter; these
perimeter pointers are stored in the link positions named CW and
CCW. Vectors never cross, arcs cross on occassions but can be fixed.
The ncnt datum of arcs and vectors contains their length.
The time line links, NTIME and PTIME, may point to a corresponding
arc or vector in the image previous or subsequent to the current
image. (The zdepth datum contains a positive number indicating
distance from the camera's image plane; the zdepth computation is
not properly implemented as of May 1973).
3. POLYGON NODE FORMAT.
_____________________________________________
word | CW | CCW |
0 | polygon ring | 3
_____|___________________|___________________|
word | DAD | SON |
1 | level | 1st vector | 3
_____|___________________|___________________|
word | type | reloc |
2 | 10 | 33 3233 |
_____|___________________|___________________|
word | ENDO | EXO |
3 |1st polygon within |polygon surround me| 3
_____|___________________|___________________|
word | ALT | ncnt |
4 | shape {or 1st arc}| number of sides | 2
_____|___________________|___________________|
word | NGON | PGON |
5 | nest bro polygon | nest sis polygon | 3
_____|___________________|___________________|
word | | |
6 | NTIME time line PTIME | 3
_____|___________________|___________________|
Every polygon belongs to a level pointed at by the DAD link;
the ring of polygons of a level is formed in the CW and CCW links;
the son of a polygon is its first vector (or arc after the polygon
has been smoothed) and that first vector has the upper left most
locus of any vector of the polygon.
The ENDO, EXO, NGON, PGON are used to form the nested
polygon tree. Every polygon has non-NIL NGON and PGON links; the
trivial case being that the polygon points at itself twice. Every
polygon except one, the outer border polygon, has a non-NIL EXO
link. Every polygon that surrounds one or more other polygons has a
non-NIL ENDO link.
The ALT link position of a polygon temporarily points to the
first arc of a polygon during smoothing when a polygon has both
vectors and arcs. The final contents of the ALT link is a pointer to
the shape node of the polygon. The ncnt datum indicates the number
of sides of the polygon.
The time line of polygons runs thru the NTIME and PTIME
links which point either to a nearly exact match of a polygon; or to
a fusion polygon of a two for one match; or to one of the two
fission parts of a one for two match; (to find the other fission
part, the time links of the vectors must be scanned).
4. SHAPE NODE FORMAT.
_____________________________________________
word | CW | CCW |
0 | fusion shape ring | 3
_____|___________________|___________________|
word | perm | area |
1 | | | 0
_____|___________________|___________________|
word | type | reloc |
2 | 10 | 30 0030 |
_____|___________________|___________________|
word | row | col |
3 | 0000.00 | 0000.00 | 0
_____|___________________|___________________|
word | pxy | mzz |
4 |product of inertia | Z-axis moment | 0
_____|___________________|___________________|
word | NGON | PGON |
5 | fusion polygon | main polygon | 3
_____|___________________|___________________|
word | mxx | myy |
6 | X-axis moment | Y-axis moment | 0
_____|___________________|___________________|
The shape node contains the data necessary for normalizing
two polygons so that only their shapes remain. In particular, the
row and col of a shape node is the center of mass of the polygon;
area is the area; perm is the length of perimeter; and mxx, myy,
mzz, pxy is the polygons inertia tensor (from which the principle
angle of orientation can be computed). When given two shapes, the
centers of mass may be alligned; the principle angles may be allign;
and the areas (or permeter) of the two may be normalized.
There are two kinds of shapes: polygon shapes and fusion
shapes. Polygon shapes correspond to a single polygon pointed at by
the PGON link. The CW, CCW and NGON links of a polygon shape are
NIL. Fusion shapes are temporary nodes belonging to a level as a
ring thru CW and CCW. Fusion shapes correspond to the summation of
two unmated polygons which are pointed to by the NGON and PGON
links. The expressions relating to the inertia tensor and to fusion
summation are given in the section on polygon comparing.
The datums named perm, area, pxy, mxx, myy, mzz contain the
left half of a PDP-10 floating number. (Technical note: half of a
floating number has 9 bits of precision and should be expanded to
full word by using the (mirabile dictu !) HLLE instruction in order
to avoid an illegal floating zero caused by truncating numbers like
-1023.0; in CRE, only the product of inertia will ever be negative).
5. LEVEL NODE FORMAT.
_____________________________________________
word | CW | CCW |
0 | level ring | 3
_____|___________________|___________________|
word | DAD | SON |
1 | image | 1st polygon | 3
_____|___________________|___________________|
word | type | reloc |
2 | | 33 0200 |
_____|___________________|___________________|
word | | |
3 | --- | --- | 0
_____|___________________|___________________|
word | ALT | ncnt |
4 | (1st fusion shape)|threshold cut level| 2
_____|___________________|___________________|
word | | |
5 | --- | --- | 0
_____|___________________|___________________|
word | | |
6 | --- | --- | 0
_____|___________________|___________________|
Every level belongs to an image pointed to by the DAD link;
the ring of levels of an image is formed in the CW and CCW links;
the son of a level is its first polygon and that first polygon is
the upper left most polygon of the level.
The ncnt datum of a level contains its threshold cut value,
which is an integer between -1 and 63. The -1 level is always
generated, and it contains a single polygon with four sides. The -1
level's polygon is called the border polygon; the fiction being that
every point beyond the edges of the televsion picture has an
intensity value of -2, which is blacker than black.
The ALT link of a level contains a temporary pointer to that
level's ring of fusion shapes during polygon compare time mating.
6. IMAGE NODE FORMAT.
_____________________________________________
word | CW | CCW |
0 | image ring | 3
_____|___________________|___________________|
word | DAD | SON |
1 | film | 1st level | 3
_____|___________________|___________________|
word | type | reloc |
2 | | 33 0000 |
_____|___________________|___________________|
word | | |
3 | --- | --- | 0
_____|___________________|___________________|
word | | |
4 | --- | --- | 0
_____|___________________|___________________|
word | | |
5 | --- | --- | 0
_____|___________________|___________________|
word | | |
6 | --- | --- | 0
_____|___________________|___________________|
Every image belongs to the film pointed to by the DAD link;
the ring of images of the film is formed in the CW and CCW links;
the son of an image is its first level and that first level is the
-1 intensity cut level of the image.
Although an affront to common sense, the counter clockwise
direction about the image ring is positive or later in time and the
clockwise direction is negative or earlier in time. I achieved this
curio by consistently adhereing to the mathematical convention of
counter clockwise as positive; and a day came when counter clockwise
around a ring of real time events was represented in the same manner
as counter clockwise around a polygonal ring of edges.
All the empty space in the image node is reserved for camera
specification data.
7. FILM NODE FORMAT.
_____________________________________________
word | | CCW |
0 | | 1st empty | 1
_____|___________________|___________________|
word | DAD | SON |
1 | 0 | 1st image | 3
_____|___________________|___________________|
word | type | reloc |
2 | | 33 0000 |
_____|___________________|___________________|
word | | |
3 | --- | --- | 0
_____|___________________|___________________|
word | | |
4 | --- | --- | 0
_____|___________________|___________________|
word | | |
5 | --- | --- | 0
_____|___________________|___________________|
word | | |
6 | --- | --- | 0
_____|___________________|___________________|
The film node is unique; it is the first node in a CRE
output file; the SON of film is its first image; the DAD of a film
is NIL; the CCW of a film is a pointer to the 1st empty node;
however, because the nodes are compacted for output and then
relocated with respect to the film node; the final empty node
pointer indicates the number of words of data in the CRE file.
8. EMPTY NODE FORMAT.
_____________________________________________
word | | CCW |
0 | --- | avail | 1
_____|___________________|___________________|
word | | |
1 | --- | --- | 0
_____|___________________|___________________|
word | type | reloc |
2 | | 00 0000 |
_____|___________________|___________________|
word | | |
3 | --- | --- | 0
_____|___________________|___________________|
word | | |
4 | --- | --- | 0
_____|___________________|___________________|
word | | |
5 | --- | --- | 0
_____|___________________|___________________|
word | | |
6 | --- | --- | 0
_____|___________________|___________________|
The list of empty nodes is maintained in the CCW link
postion; the last empty node contains a zero or NIL link. At present
all the other words of an empty node are zero.
FIGURE SHOWING RASTER STRUCTURE._____________________________________
↑
↑
NORTH
grid point R,C R,C+1
o____HSEG______o
|
|
|
←←←WEST VSEG PIXEL(R,C) EAST→→→
|
|
|
o SOUTH
R+1,C ↓
↓
_____________________________________________________________________
DATA STRUCTURE: IMAGE ARRAYS.
There are five arrays in CRE: TVBUF, Television Buffer; PAC,
Picture Accumulator; VSEG, vertical segments; HSEG, horizontal
segments; and SKY, background sky blue array. The dimensions are:
FIVE ARRAYS.
1. TVBUF - 216 rows, 288 columns of 6 bit bytes.
2. PAC - 216 rows, 288 columns of 1 bit bytes.
3. VSEG - 216 rows, 289 columns of 1 bit bytes.
4. HSEG - 217 rows, 288 columns of 1 bit bytes.
5. SKY - 216 rows, 289 columns of 18 bit bytes.
Inside CRE, the video image size was fixed at 216 rows of
288 columns of 6 bits per pixel. My original idea was to write a
vision operator that would be applied on a small fixed sized window;
so I have had windows 2 by 2; 2 by 3; 4 by 9; 32 by 36; 72 by 96;
and 216 by 288. That is 216=2*2*2*3*3*3 and 288=2*2*2*2*2*3*3.
Having a fixed window size avoids a morass of word packing, array
allocation and window splicing. Having a window size constructed
out of powers of 2 and 3 simplifies what word packing is required
and allows me to do area and space computations in my head.
The image arrays of CRE are of course two dimensional with
the coordinates in row and columns. Row number increases going down
image, in the negative Y axis direction, which is also called the
direction south. Column numbers increase going right on the image,
in the positive X axis direction, which is also called the direction
east. Video picture elements, or "pixels" are thought of as
expressing the intensity of a square cell; the cells are numbered
from 0 to 215 rows, 0 to 287 columns; the number of a cell is the
grid locus of its upper left (northwest) corner; the center locus of
a cell is at (row+1/5,col+1/2). A pixel cell is surrounded by four
segments; the horizontal segments are numbered 0 to 216 rows, 0 to
287 columns; the number of an HSEG is the grid locus of its left
(west) end point. The vertical segments are numbered 0 to 215 rows,
0 to 288 columns; the number of a VSEG is the grid locus of its
upper (north) end point. These conventions are suggested in the
diagram at the bottom of page 19.